#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 20

int n;
int countNum = 0;
int sum = 0, product = 1;

vector<int> A;
vector<int> lucky;

void f(int pos)
{
    for (int i = pos; i < n; i++)
    {
        sum += A[i];
        product *= A[i];
        lucky.push_back(A[i]);
        if (sum > product)
        {
            for (int val : lucky)
                cout << val << " ";
            cout << endl;
            countNum++, f(pos + 1);
        }
        else if (A[i] == 1) // 单独一个1虽然不满足条件，但是后续加入后可能满足
            f(pos + 1);
        else
            break;

        sum -= A[i];
        product /= A[i];
        lucky.pop_back();
        while (i < n && A[i] == A[i + 1]) // 跳过重复的值
            i++;
    }
}

int main()
{
    cout << "请输入袋中数字数量n=";
    cin >> n;
    cout << "请输入" << n << "个数：" << endl;
    for (int i = 1; i <= n; i++)
    {
        int tmp;
        cin >> tmp;
        A.push_back(tmp);
    }
    cout << endl;
    std::sort(A.begin(), A.end());

    f(0);
    cout << "一共有" << countNum << "种幸运袋子" << endl;
    return 0;
}

/*
请输入袋中数字数量n=4
请输入4个数：
1 1 2 3

1 1
1 1 2
1 1 2 3
1 1 3
一共有4种幸运袋子
*/